import javax.swing.tree.TreeNode;

/*
 * @lc app=leetcode.cn id=98 lang=java
 *
 * [98] 验证二叉搜索树
 *
 * https://leetcode-cn.com/problems/validate-binary-search-tree/description/
 *
 * algorithms
 * Medium (35.30%)
 * Likes:    1381
 * Dislikes: 0
 * Total Accepted:    403.1K
 * Total Submissions: 1.1M
 * Testcase Example:  '[2,1,3]'
 *
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * 
 * 有效 二叉搜索树定义如下：
 * 
 * 
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [2,1,3]
 * 输出：true
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 树中节点数目范围在[1, 10^4] 内
 * -2^31 <= Node.val <= 2^31 - 1
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    // 采用Morris中序遍历，二叉搜索树的中序遍历结果一定是升序的
    // public boolean isValidBST(TreeNode root) {
    //     if (root == null || root.left == null && root.right == null) {
    //         return true;
    //     }
    //     Long preVal = Long.MIN_VALUE;
    //     Long curVal = (long) 0;
    //     boolean ret = true;
    //     while (root != null) {
    //         if (root.left != null) {
    //             // 暂存左子树的左节点
    //             TreeNode temp = root.left;
    //             // temp.right != root 表示已经建立连接了
    //             // 若没有建立连接且，则一直到左子树的最右节点
    //             while (temp.right != null && temp.right != root) {
    //                 temp = temp.right;
    //             }
    //             // 走到最右节点的情况
    //             if (temp.right == null) {
    //                 // 让其右指针与root建立连接
    //                 temp.right = root;
    //                 // 往左走继续建立连接
    //                 root = root.left;
    //             } 
    //             // 已经建立了连接的情况 (说明根节点的左子树已经访问完毕)
    //             else {
    //                 curVal = (long)root.val;
    //                 if (curVal <= preVal) {
    //                     ret = false;
    //                     break;
    //                 }
    //                 preVal = curVal;
    //                 // 断开连接
    //                 temp.right = null;
    //                 // 接着访问下一个节点
    //                 root = root.right;
    //             }
    //         } 
    //         // 没有左子树，直接输出并访问右子树
    //         else {
    //             curVal = (long)root.val;
    //             if (curVal <= preVal) {
    //                 ret = false;
    //                 break;
    //             }
    //             preVal = curVal;
    //             root = root.right;
    //         }
    //     }
    //     return ret;
    // }

    // 递归
    // 要点是传入每个节点允许值的范围
    public boolean validate(TreeNode root, Integer low, Integer high) {
        // Empty trees are valid BSTs.
        if (root == null) {
            return true;
        }
        // The current node's value must be between low and high.
        if ((low != null && root.val <= low) || (high != null && root.val >= high)) {
            return false;
        }
        // The left and right subtree must also be valid.
        return validate(root.right, root.val, high) && validate(root.left, low, root.val);
    }

    public boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }
}
// @lc code=end

